package com.github.yangyishe.p200;

import com.github.yangyishe.ListNode;

/**
 * 155. 最小栈
 * https://leetcode.cn/problems/min-stack/?envType=study-plan-v2&envId=top-interview-150
 *
 * 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
 *
 * 实现 MinStack 类:
 *
 * MinStack() 初始化堆栈对象。
 * void push(int val) 将元素val推入堆栈。
 * void pop() 删除堆栈顶部的元素。
 * int top() 获取堆栈顶部的元素。
 * int getMin() 获取堆栈中的最小元素。
 *
 *
 * 示例 1:
 *
 * 输入：
 * ["MinStack","push","push","push","getMin","pop","top","getMin"]
 * [[],[-2],[0],[-3],[],[],[],[]]
 *
 * 输出：
 * [null,null,null,null,-3,null,0,-2]
 *
 * 解释：
 * MinStack minStack = new MinStack();
 * minStack.push(-2);
 * minStack.push(0);
 * minStack.push(-3);
 * minStack.getMin();   --> 返回 -3.
 * minStack.pop();
 * minStack.top();      --> 返回 0.
 * minStack.getMin();   --> 返回 -2.
 *
 *
 * 提示：
 *
 * -231 <= val <= 231 - 1
 * pop、top 和 getMin 操作总是在 非空栈 上调用
 * push, pop, top, and getMin最多被调用 3 * 104 次
 */
public class Problem155 {
    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        System.out.println(minStack.getMin());
        minStack.pop();
        System.out.println(minStack.top());
        System.out.println(minStack.getMin());

    }

}

/**
 * 最小栈
 * 思路:
 * 1. 使用链表记录最小栈
 * 2. 在存储原始栈的同时, 存储一个最小值的栈, 记录size和最小值
 */
class MinStack {
    ListNode data;
    MinVal minVal;
    int size;

    public MinStack() {

    }

    public void push(int val) {
        size++;
        if(data==null){
            data=new ListNode(val);
            minVal=new MinVal(val,1);
        }else{
            data= new ListNode(val,data);
            if(minVal.val>val){
                minVal=new MinVal(val,size,minVal);
            }
        }
    }

    public void pop() {
        if(data!=null){
            size--;
            data=data.next;
            if(minVal.size>size){
                minVal=minVal.sub;
            }
        }
    }

    public int top() {
        return data!=null?data.val:0;
    }

    public int getMin() {
        return minVal!=null?minVal.val:0;
    }
}
class MinVal{
    // 最小值
    int val;
    // 记录此值的下标
    int size;
    // 次小值
    MinVal sub;

    public MinVal(int val, int size) {
        this.val = val;
        this.size = size;
    }

    public MinVal(int val, int size, MinVal sub) {
        this.val = val;
        this.size = size;
        this.sub = sub;
    }
}
/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */